package com.wtgroup.demo.leetcode.q060_排列序列_第k个排列;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.concurrent.atomic.AtomicInteger;

public class Q060_My1 {

    /*
    * 回溯方式
    * 效率: 超时. k 越大, 耗时越高.
    * n=15, k=134232353, 耗时 33938ms.
    * */

    public String getPermutation(int n, int k) {
        ArrayDeque<String> path = new ArrayDeque<>();
        boolean[] used = new boolean[n+1];
        AtomicInteger cnt = new AtomicInteger();
        String res = func(n, path, used, cnt, k);
        return res;
    }

    private String func(int n, Deque<String> path, boolean[] used, AtomicInteger cnt, int maxCnt) {
        if (path.size() == n) {
            cnt.incrementAndGet();
            return String.join("", path);
        }

        for (int i = 1; i <= n; i++) {
            if(used[i]) continue;
            path.addLast(i + "");
            used[i] = true;
            String ret = func(n, path, used, cnt, maxCnt);
            if (cnt.get()==maxCnt) {
                return ret;
            }
            path.removeLast();
            used[i] = false;
        }

        return null; // not here
    }


}
